The need to evaluate a function at a variety of points arises for example in color image processing. To process an image, each pixel of the image is mapped from its present color value to a new color value determined by a function which defines the desired image transformation. For example, to transform the pixel value R, G, B, a first function F.sub.R (R, G, B) is evaluated at the point in the color space defined by the coordinates R, G, B to form a transformed value for the red color component R.sub.T =F.sub.R (R, G, B). Similarly, the function F.sub.G (R, G, B) is computed to derive the green color component G.sub.T =F.sub.G (R, G, B); and the function F.sub.B (R, G, B) is computed to derive the blue color component B.sub.T.
In a typical image, many pixels have the same color value. For example, an image having two million pixels may include only several hundred thousand unique color values. Accordingly, if each pixel of the image is independently processed, several million redundant evaluations of each function may be performed.
Caching schemes have been used for storing precomputed values of a function for later reuse. One type of caching scheme saves the precomputed function value for every unique input value in the function's domain. A second type stores only the precomputed function values for selected input values.
Caching schemes of the first type are typically used for functions that have a small number of unique input values. In this case, the size of the data area needed to store the computed results for each possible input value is reasonably small.
Caching schemes of the second type are typically used for functions that have a large number of unique input values. For these functions, an extremely large data area is required to store precomputed values for every point in the function's domain. To reduce the storage requirements, the cache saves only precomputed function values for selected input values which are most likely to be required.
Various methods have been used to select which precomputed values to save. A simple method saves only the function values for the most recently processed input values. Another method saves only the most frequently processed input values.
Neither of the above described caching schemes are useful when applied to functions which require little time to compute but which have extremely large domains. First, the time f.sub.T required to compute the result of the function for a single input value is very small. Accordingly, for the cache to be effective, the time to fetch the precomputed value from the cache must be extremely small. Otherwise, it is faster to simply recompute the function.
Second, since the potential number of unique input values for the functions is very large, an extremely large data area is required to store a precomputed function value for each possible input value. The size of the data area can be reduced through the use of dynamic memory allocation, complex data structures, or by selection algorithms which save the function values for selected input values. However, these procedures require substantial time to dynamically allocate memory, traverse linked lists, search trees, and/or search hash tables. Further, they require significant time to select which computed function values to save.
Therefore, one object of the present invention is to store a function value only after it has been requested and computed in the course of performing a given transformation. Another object is to quickly determine which function values have already been computed and, upon the occurrence of a redundant input value, retrieve the previously computed value from storage. Yet another object is to achieve these ends without using substantial portions of computer memory and without requiring substantial processing resources for storing and retrieving function values.